Feature #11: Generate Movie Viewing Orders

Implementing the "Generate Movie Viewing Orders" feature for our "Netflix" project.

Description#

We want to offer marathons for our viewers. Each marathon will have a fixed set of movies catering to a specific taste. For a given marathon, different viewing orders of the movies will yield different user satisfaction results. We want to experiment (A/B testing) with different viewing orders of the same marathon.

Your task is to generate all the possible permutations of movies in a given marathon.

Let’s look at an example to better understand this:

[
[
Frozen
Frozen
Dune
Dune
Coco
Coco
]
]
[
[
[
[
Frozen
Frozen
Dune
Dune
Coco
Coco
]
]
[
[
]
]
Frozen
Frozen
Coco
Coco
Dune
Dune
[
[
]
]
Dune
Dune
Frozen
Frozen
Coco
Coco
Dune
Dune
Coco
Coco
Frozen
Frozen
Coco
Coco
Frozen
Frozen
Dune
Dune
Coco
Coco
Dune
Dune
Frozen
Frozen
[
[
[
[
[
[
]
]
]
]
]
]
]
]
Input:
Input:
Permutations:
Permutation...
Viewer does not support full SVG 1.1
Permutation example

Solution#

To solve this problem, we will use the backtracking approach.

We will assume a backtrack function that takes the index of the first movie to consider as an argument backtrack(first).

  • If the first movie to consider has index n, then that means that the current permutation is done.

  • We will iterate over the marathon from index first to index n - 1.

  • We will place the ith movie first in the permutation, that is, movies[first], movies[i] = movies[i], movies[first].

  • We will proceed to create all the permutations that start from the ith movie: backtrack(first + 1).

  • Now we will backtrack, that is, movies[first], movies[i] = movies[i], movies[first] back.

Let’s look at some illustrations to better understand this:

Note: We are using numbers to represent movies in the following illustration.

Created with Fabric.js 3.6.6

1 of 14

Created with Fabric.js 3.6.6

2 of 14

Created with Fabric.js 3.6.6

3 of 14

Created with Fabric.js 3.6.6

4 of 14

Created with Fabric.js 3.6.6

5 of 14

Created with Fabric.js 3.6.6

6 of 14

Created with Fabric.js 3.6.6

7 of 14

Created with Fabric.js 3.6.6

8 of 14

Created with Fabric.js 3.6.6

9 of 14

Created with Fabric.js 3.6.6

10 of 14

Created with Fabric.js 3.6.6

11 of 14

Created with Fabric.js 3.6.6

12 of 14

Created with Fabric.js 3.6.6

13 of 14

Created with Fabric.js 3.6.6

14 of 14

Let’s look at the code for this solution:

Generate movie viewing orders

Complexity measures#

Time complexity Space complexity
O(n!){O}(n!) O(n){O}(n)

Time complexity#

The algorithm takes O(n!){O}(n!) time complexity, wherein nn is the movies size and n!=n(n1)(n2)(n3)321.{\displaystyle n!=n\cdot (n-1)\cdot (n-2)\cdot (n-3)\cdot \cdots \cdot 3\cdot 2\cdot 1\,.}

Space complexity#

The algorithm will take O(n){O}(n) space complexity because the maximum stack depth is nn, the height of any branch from the root to any leaf.

Feature #10: Calculate Median of Buffering Events

Feature #12: Maintain Continue Watching Bar